package oj;

import java.util.Arrays;

public class LC322 {
    public int coinChange(int[] coins, int amount) {
        //dp数组的含义：当目标金额为i时，至少需要dp[i]枚硬币
        int[] dp=new int[amount+1];
        Arrays.fill(dp,amount+1);
        dp[0]=0;
        for(int i=1;i<dp.length;i++){
            for(int coin:coins){
                if(i-coin<0){
                    continue;
                }else{
                    dp[i]=Math.min(dp[i],1+dp[i-coin]);
                }
            }

        }
        return dp[amount]==amount+1?-1:dp[amount];
    }
}
